It is shown that the counting function of n Boolean variables can beimplemented with the formulae of size O(n^3.06) over the basis of all 2-inputBoolean functions and of size O(n^4.54) over the standard basis. The samebounds follow for the complexity of any threshold symmetric function of nvariables and particularly for the majority function. Any bit of the product ofbinary numbers of length n can be computed by formulae of size O(n^4.06) orO(n^5.54) depending on basis. Incidentally the bounds O(n^3.23) and O(n^4.82)on the formula size of any symmetric function of n variables with respect tothe basis are obtained.
展开▼
